import java.util.*;
public class test {
    // leetcode 79.单词搜索
    class Solution {
        //用于标记路径,防止一条路来回走
        public boolean[][] count;
        public char[][] nums;
        public char[] str;
        public int len;
        public int col;
        public int row;

        public boolean exist(char[][] board, String word) {
            col = board[0].length;
            row = board.length;
            len = word.length();
            //剪枝优化
            if(row * col < len){
                return false;
            }
            count = new boolean[row][col];
            nums = board;
            str = word.toCharArray();
            char c = str[0];
            boolean flg = false;
            //先搜索第一个目标字母
            for(int i = 0;i < row;i++){
                for(int j = 0;j < col;j++){
                    if(board[i][j] == c){
                        //沿着该字符开始搜索
                        count[i][j] = true;
                        flg = dfs(i,j,1);
                        if(flg){
                            return true;
                        }
                        count[i][j] = false;
                    }
                }
            }
            return false;
        }
        public boolean dfs(int r,int c,int ind){
            if(ind == len){
                return true;
            }
            //代表上下左右四个坐标
            int[] dx = {0,0,1,-1};
            int[] dy = {1,-1,0,0};
            for(int i = 0;i < 4;i++){
                int x = dx[i] + r;
                int y = dy[i] + c;
                // 1. 控制边界情况,x,y不能越界
                // 2. 判断该字符是否被使用过
                // 3. 判断这个字符是否为目标字符
                if(x >= 0 && x < row && y >= 0 && y < col && !count[x][y] && nums[x][y] == str[ind]){
                    count[x][y] = true;
                    if(dfs(x,y,ind + 1)){
                        return true;
                    }
                    count[x][y] = false;
                }
            }
            return false;
        }
    }
    // leetcode 1219.黄金矿工
    class Solution {
        public int[][] nums;
        public boolean[][] count;
        public int row;
        public int col;
        public int sum = 0;
        public int max = 0;
        public int getMaximumGold(int[][] grid) {
            row = grid.length;
            col = grid[0].length;
            count = new boolean[row][col];
            nums = grid;
            for(int i = 0;i < row;i++){
                for(int j = 0;j < col;j++){
                    if(nums[i][j] != 0){
                        count[i][j] = true;
                        sum += nums[i][j];
                        dfs(i,j);
                        max = Math.max(sum,max);
                        count[i][j] = false;
                        sum -= nums[i][j];
                    }
                }
            }
            return max;
        }
        public void dfs(int r,int c){
            if(r == row || c == col){
                return;
            }
            int[] dx = {0,0,1,-1};
            int[] dy = {1,-1,0,0};
            for(int i = 0;i < 4;i++){
                int x = r + dx[i];
                int y = c + dy[i];
                // 1. 此次路线未被探索过
                // 2. 此格拥有黄金
                // 3. x,y没有越界
                if(x >= 0 && x < row && y >= 0 && y < col && !count[x][y] && nums[x][y] != 0){
                    sum += nums[x][y];
                    count[x][y] = true;
                    max = Math.max(max,sum);
                    dfs(x,y);
                    sum -= nums[x][y];
                    count[x][y] = false;
                }
            }
            return;
        }
    }
}
